/*
 * @Author: liusheng
 * @Date: 2022-05-02 22:00:08
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-02 22:19:51
 * @Description: 剑指 Offer II 053. 二叉搜索树中的中序后继
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 * 剑指 Offer II 053. 二叉搜索树中的中序后继
给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。

节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。

 

示例 1：
          2
         / \
        1   3


输入：root = [2,1,3], p = 1
输出：2
解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。
示例 2：



输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。
 

提示：

树中节点的数目在范围 [1, 104] 内。
-105 <= Node.val <= 105
树中各节点的值均保证唯一。
 

注意：本题与主站 285 题相同： https://leetcode-cn.com/problems/inorder-successor-in-bst/

通过次数14,165提交次数22,422
 */

// Definition for a binary tree node.
struct TreeNode {
    int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/*dfs solution,use the visited to mark the node p has been visited,record the p's successor node*/
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        inorderTraverse(root,p);
        return successorNode;
    }
private:
    void  inorderTraverse(TreeNode* root, TreeNode* p)
    {
        if (!root)
        {
            return;
        }

        inorderSuccessor(root->left,p);

        if (visited)
        {
            visited = false;
            successorNode = root;
            return;
        }

        if (root == p)
        {
            // printf("rootval:%d,pval:%d\n",root->val,p->val);
            visited = true;
        }

        inorderSuccessor(root->right,p);
    }
private:
    bool visited = false;
    TreeNode * successorNode =  nullptr;
};

class Solution2 {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode * node = root;
        TreeNode * successor = nullptr;
        while (node)
        {
            //if node->val > p->val,continue move to left
            //to find the minist value larger than p->val
            if (node->val > p->val)
            {
                successor = node;
                node = node->left;
            }
            else //node->val <= p->val
            {
                node = node->right;
            }
        }

        return successor;
    }
};
